package LeetCode2018;

import java.util.HashMap;
import java.util.Map;

/**
 * Examples:

 Given "abcabcbb", the answer is "abc", which the length is 3.

 Given "bbbbb", the answer is "b", with the length of 1.

 Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

   最长无重复子串
 * @leiwenkang 2018-03-30 15:38.
 */
public class LeetCode003 {
    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcadbcbb"));
    }

    public static int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] ch = s.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        int max = 0;
        int start = 0;
        for (int i = 0; i < ch.length; i++) {
            if (map.containsKey(ch[i]) && map.get(ch[i]) >= start) {
                int length = i - start;
                if (length > max) {
                    max = length;
                }
                start = map.get(ch[i]) + 1;
            }
            map.put(ch[i], i);
        }
        if (ch.length - start > max) {
            max = ch.length - start;
        }
        return max;
    }
}
